/* ************************************************************************
> File Name:     BFS.c
> Author:        zhfu
> mail:          3346897597@qq.com
> Created Time:  2022年04月19日 星期二 09时39分04秒
> Description:   
 ************************************************************************/
#include<stdio.h>
#define MAX_ROW 5
#define MAX_COL 5
/*本队列只是改变指针指向的位置，并不覆盖原先存在的元素，这样便于指定前驱点的位置所在，pre表示前驱点在队列中的位置*/
struct pointer {
    int row, col, pre;
};

/*队列和栈类似包括七部分，队列的存储空间，头尾指针，enqueue和dequeue操作以及检查空和满*/
struct pointer queue[25];
int head = 0, tail = 0;

void enqueue(struct pointer p)
{
    queue[tail++] = p;
}

struct pointer dequeue()
{
    return queue[head++];
}

int is_empty()
{
    return head == tail;
}

int maze[MAX_ROW][MAX_COL] = {
	0, 1, 0, 0, 0,
	0, 1, 0, 1, 0,
	0, 0, 0, 0, 0,
	0, 1, 1, 1, 0,
	0, 0, 0, 1, 0,
};

int cnt = 0;/*为了更直观表现每次print_maze，用来标号*/

void print_maze(void)
{
    int i, j;
    printf("-------%d----------\n", cnt++);
    for (i = 0; i < MAX_ROW; ++i){
        for (j = 0; j < MAX_COL; ++j){
            printf("%d ", maze[i][j]);
        }
        putchar('\n');
    }
    printf("*****************\n");
}

void visit(int row, int col)
{
    struct pointer visit_pointer = {row, col, head - 1}; /*前驱点就是上一个dequeue的点，dequeue会导致head+1,所以head-1就是前驱点，注意不能改变head*/
    maze[row][col] = 2;
    enqueue(visit_pointer);
}

int main()
{
    struct pointer p = {0, 0, -1}; /*起点*/
    maze[0][0] = 2;
    enqueue(p);

    while (!is_empty()){
        p = dequeue();
        if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1)
            break;
        if (p. row + 1 < MAX_ROW && maze[p.row + 1][p.col] == 0)
            visit(p.row + 1, p.col);
        if (p.col + 1 < MAX_COL && maze[p.row][p.col + 1] == 0)
            visit(p.row, p.col + 1);
        if (p.row - 1 >= 0 && maze[p.row - 1][p.col] == 0)
            visit(p.row - 1, p.col);
        if (p.col - 1 >= 0 && maze[p.row][p.col - 1] == 0)
            visit(p.row, p.col - 1);
        print_maze();
    }

    if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1){
        while (p.pre != -1){
            printf("(%d, %d) ", p.row, p.col);
            p = queue[p.pre];
        }
        printf("(%d, %d)\n", p.row, p.col);
    }

}
